package ex2.LinkedBinaryTree;

import java.util.*;

public class PrefixToPostfix {
    public Stack<LinkedBinaryTree> expre;   // 操作数栈
    public Stack<String> op;    // 运算符栈
    public String result = "";

    public PrefixToPostfix()
    {
        expre = new Stack<LinkedBinaryTree>();
        op = new Stack<String>();
    }

    private LinkedBinaryTree getOperand(Stack<LinkedBinaryTree> treeStack)
    {
        LinkedBinaryTree temp;
        temp = treeStack.pop();

        return temp;
    }

    public String convert(String expression) {
        LinkedBinaryTree operand1;
        LinkedBinaryTree operand2;

        StringTokenizer stringTokenizer = new StringTokenizer(expression);

        String tempToken;

        while (stringTokenizer.hasMoreTokens()) {
            tempToken = stringTokenizer.nextToken();

            // 处理括号
            if (tempToken.equals("(")) {
                op.push(tempToken);
                tempToken = stringTokenizer.nextToken();

                while (!tempToken.equals(")")) {
                    if (tempToken.equals("+") || tempToken.equals("-")) {
                        if (!op.isEmpty()) {
                            // 栈不空，判断“(”
                            if (op.peek().equals("("))
                                op.push(tempToken);
                            else {
                                String b = op.pop();
                                operand1 = getOperand(expre);
                                operand2 = getOperand(expre);
                                LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                                expre.push(a);
                                op.push(tempToken);
                            }
                        } else {
                            // 栈为空，运算符入栈
                            op.push(tempToken);
                        }
                    } else if (tempToken.equals("*") || tempToken.equals("/")) {
                        if (!op.isEmpty()) {
                            if (op.peek().equals("*") || op.peek().equals("/")) {
                                String b = op.pop();
                                operand1 = getOperand(expre);
                                operand2 = getOperand(expre);
                                LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                                expre.push(a);
                                op.push(tempToken);
                            } else {
                                op.push(tempToken);
                            }
                        }
                    } else {
                        // 操作数入栈
                        LinkedBinaryTree a = new LinkedBinaryTree(tempToken);
                        expre.push(a);
                    }
                    tempToken = stringTokenizer.nextToken();
                }

                while (true) {
                    String b = op.pop();
                    if (!b.equals("(")) {
                        operand1 = getOperand(expre);
                        operand2 = getOperand(expre);
                        LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                        expre.push(a);
                    } else {
                        // 终止循环
                        break;
                    }
                }
            }
            else if (tempToken.equals("+") || tempToken.equals("-")) {
                if (!op.isEmpty()) {
                    String b =  op.pop();
                    operand1 = getOperand(expre);
                    operand2 = getOperand(expre);
                    LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                    expre.push(a);
                    op.push(tempToken);
                } else {
                    op.push(tempToken);
                }
            } else if (tempToken.equals("*") || tempToken.equals("/")) {
                    if (!op.isEmpty()) {
                        if (op.peek().equals("*") || op.peek().equals("/"))
                        {
                            String b = op.pop();
                            operand1 = getOperand(expre);
                            operand2 = getOperand(expre);
                            LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                            expre.push(a);
                            op.push(tempToken);
                        }
                        else
                        {
                            op.push(tempToken);
                        }
                    }else {
                        op.push(tempToken); // 如果栈为空，运算符入栈
                    }
            }
                else
                {
                    LinkedBinaryTree a = new LinkedBinaryTree(tempToken);
                    expre.push(a);
                }
        }

        while (!expre.isEmpty() && !op.isEmpty()) {
            String b = op.pop();
            operand1 = getOperand(expre);
            operand2 = getOperand(expre);
            LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
            expre.push(a);
        }

        Iterator postTree = expre.peek().iteratorPostOrder();

        System.out.println("后缀表达式：");

        while (postTree.hasNext())
        {
            result += postTree.next() + " ";
        }
        return result;
    }

    public String getTree()
    {
        return (expre.peek()).toString();
    }

}
